/**
 * Copyright (c) 2010 Simple Graph Tools contributors. All rights reserved.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * $Id$
 */
package org.sgt.coredef.util;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.eclipse.emf.common.util.EList;
import org.sgt.coredef.Chain;
import org.sgt.coredef.CoredefFactory;
import org.sgt.coredef.DecomposableNode;
import org.sgt.coredef.Edge;
import org.sgt.coredef.Node;

/**
 * @author Anne BUTTIGHOFFER <BR/>
 * <BR/>
 *         HISTORY :<BR/>
 *         <UL>
 *         <LI>Creation 090430 Anne BUTTIGHOFFER</LI>
 *         <LI>Refactoring 090505 Frederick MINATCHY removed references to
 *         walker.</LI>
 *         </UL>
 * 
 */
public class GraphSequencer {

	/**
	 * The maximum decomposition number allowed (arbitrary to make sure this
	 * sequencer won't loop forever...
	 */
	public static final int MAX_DECOMP = 30;

	/**
	 * Caches the route -> chains set map.
	 */
	private Map<Route, Set<Chain>> routes2ChainsMap
		= new HashMap<Route, Set<Chain>>();

	/**
	 * Caches the route -> sequenced chains set map.
	 */
	private Map<Route, Set<Chain>> sequencedMap
		= new HashMap<Route, Set<Chain>>();

	/**
	 * Our Sequencer's myPolicy.
	 * 
	 * @see IGraphWalkerPolocy
	 */
	private IGraphSequencerPolicy myPolicy;

	/**
	 * Constructor.
	 * 
	 * @param map
	 *            the map of Chains to sequence by routes.
	 */
	public GraphSequencer(final Map<Route, Set<Chain>> map) {
		// Checking we have a valid Map
		if (GraphSequencer.isValidMap(map)) {
			this.routes2ChainsMap = map;
		}
	}

	/**
	 * @return the cached value of {@link #routes2ChainsMap}.
	 */
	public final Map<Route, Set<Chain>> getRoutes2ChainsMap() {
		return routes2ChainsMap;
	}

	/**
	 * @return the cached value of {@link #myPolicy}.
	 */
	public final IGraphSequencerPolicy getPolicy() {
		return myPolicy;
	}

	/**
	 * Defines the {@link IGraphSequencerPolicy} of this sequencer.
	 * @param policy {@link IGraphSequencerPolicy}.
	 */
	public final void setPolicy(final IGraphSequencerPolicy policy) {
		if (policy != null) {
			if (this.sequencedMap != null) {
				clearSequencedMap();
			}
			this.myPolicy = policy;
		}
	}

	/**
	 * @return the cached value of  {@link #sequencedMap}.
	 */
	public final Map<Route, Set<Chain>> getSequencedMap() {
		return sequencedMap;
	}

	/**
	 * Resets this {@link #sequencedMap} to null.
	 */
	public final void clearSequencedMap() {
		this.sequencedMap = null;
	}

	/**
	 * Attempts to sequence the graph {@link #routes2ChainsMap} as determined by
	 * the myPolicy {@link #myPolicy}, and return the result.<BR/>
	 * The operation is done in two steps :
	 * <UL>
	 * <LI>first this sequencer analyzes the graph thanks to the semantics
	 * defined by the myPolicy in order to build a decomposable graph.</LI>
	 * <LI>then this decomposable graph is sequenced by the myPolicy.</LI>
	 * </UL>
	 * The result of the sequencing is then returned and the result of the
	 * analysis is stored in {@link #sequencedMap} (subsequent calls to sequence
	 * will use this cached value).
	 * 
	 * @return IGraphSequence<?> the sequences created by this graph (as defined
	 *         by the myPolicy) may be null.
	 */
	public final IGraphSequence sequence() {
		if (myPolicy != null && routes2ChainsMap != null
				& !routes2ChainsMap.isEmpty()) {

			Map<Route, Set<Chain>> sequenceableMap
				= new HashMap<Route, Set<Chain>>();

			// First analyze our graph's Join/fork semantics (as determined by
			// the myPolicy)
			if (sequencedMap == null) {
				for (Route route : routes2ChainsMap.keySet()) {
					// looping on all designated routes...
					Set<Chain> myChains = new HashSet<Chain>(routes2ChainsMap
							.get(route));
					Map<Route, Set<Chain>> map 
						= computeSimpleJoinForkMap(myChains);
					int iDecomp = 0;
					Set<Chain> seqChains = new HashSet<Chain>();
					if (map != null
							&& !map.isEmpty()
							&& !map.get(map.keySet().iterator().next())
									.isEmpty()) {
						// Limit decomposition to a cycle of MAX_DECOMP
						// sub decomposition just to make sure we do not
						// loop for ever...
						while (isDecomposable(map)
								&& iDecomp < GraphSequencer.MAX_DECOMP) {
							seqChains = compose(map);
							map = computeSimpleJoinForkMap(seqChains);
							iDecomp++;
						}
					} else {
						seqChains = myChains;
					}
					Logger.log("-----------------------------------------");
					Logger.log("      Chains to sequence : ");
					for (Chain chain : seqChains) {
						Logger.log(ChainHelper.stringRepresentation(chain));
					}
					Logger.log("-----------------------------------------");

					sequenceableMap.put(route, seqChains);
				}
				sequencedMap = sequenceableMap;
			}

			// Now delegate the production of real sequences
			// to the myPolicy and return result.

			IGraphSequence graphSequence = myPolicy.initSequence();
			myPolicy.buildSequence(graphSequence, sequencedMap);
			return graphSequence;
		}
		return null;
	}

	/**
	 * Determines whether given Map is decomposable : 
	 * there is more than one chain in one of the sets.
	 * @param map {@link Map<Route, Set<Chain>> }.
	 * @return true only is there is more than one chain
	 * in one of the sets.
	 */
	public final boolean isDecomposable(final Map<Route, Set<Chain>> map) {
		if (map == null || map.isEmpty()) {
			return false;
		}
		for (Route route : map.keySet()) {
			Set<Chain> chains = map.get(route);
			if (chains.size() > 1) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Computes the Chains corresponding to each join/fork route
	 * of the given set of chains.
	 * @param chains {@link Chain}.
	 * @return the joinFork Chains map.
	 */
	public final Map<Route, Set<Chain>> computeSimpleJoinForkMap(
			final Set<Chain> chains) {
		if (chains == null || chains.isEmpty() || myPolicy == null) {
			return null;
		}

		Map<Route, Set<Chain>> map = new HashMap<Route, Set<Chain>>();

		for (Chain chain : chains) {
			Node end = chain.getEndNode();
			Node current = chain.getStartNode();
			Node myNextNode = ChainHelper.nextNode(chain, current);
			while (myNextNode != end && myNextNode != null) {
				// Finding next Joining Node on this chain...
				int myNextNodeIndex = chain.getNodes().indexOf(myNextNode);
				Node nextJoin = getNextJoin(chain, myNextNode, chains);
				int nextJoinIndex = chain.getNodes().indexOf(nextJoin);
				Node nextFork = getNextFork(chain, myNextNode, chains);
				int nextForkIndex = chain.getNodes().indexOf(nextFork);
				if (nextJoinIndex >= nextForkIndex && nextForkIndex != -1) {
					// Fork before join...
					// but we may have another fork between them in which case
					// we should not use this join/fork couple...
					Node betterFork = getPreviousFork(chain, nextJoin, chains);
					int betterForkIndex = chain.getNodes().indexOf(betterFork);
					if (betterFork == null 
							|| betterForkIndex <= nextForkIndex) {
						Route route = new Route(nextFork, nextJoin);
						Set<Chain> routeChains = map.get(route);
						if (routeChains == null) {
							routeChains = new HashSet<Chain>();
						}
						routeChains.add(chain);
						map.put(route, routeChains);
					} else {
						// using betterFork
						Route route = new Route(betterFork, nextJoin);
						Set<Chain> routeChains = map.get(route);
						if (routeChains == null) {
							routeChains = new HashSet<Chain>();
						}
						routeChains.add(chain);
						map.put(route, routeChains);
					}
					if (myNextNodeIndex < nextJoinIndex) {
						myNextNode = nextJoin;
					} else {
						// we are finished
						myNextNode = end;
					}
				} else {
					// Join before Fork...
					if (myNextNodeIndex < nextForkIndex) {
						// goto Fork...
						myNextNode = nextFork;
					} else {
						// we are finished
						myNextNode = end;
					}
				}
			}
		}
		return map;
	}

	/**
	 * Builds the set of decomposable chains associated to the given
	 * join/fork decomposition.
	 * @param simplificationMap {@link Map<Route, Set<Chain>>}.
	 * @return the decomposable chains.
	 */
	public final Set<Chain> compose(
			final Map<Route, Set<Chain>> simplificationMap) {

		if (simplificationMap == null 
				|| simplificationMap.isEmpty()
				|| myPolicy == null) {
			return null;
		}

		Map<Route, Set<Chain>> myMap = new HashMap<Route, Set<Chain>>(
				simplificationMap);

		Set<Chain> seqChains = new HashSet<Chain>();
		for (Route route : myMap.keySet()) {
			Node fork = route.getSource();
			Node join = route.getDestination();
			Set<Chain> originals = new HashSet<Chain>(myMap.get(route));
			DecomposableNode decompNode = CoredefFactory.eINSTANCE
					.createDecomposableNode();
			Edge fork2Decomp = myPolicy.createEdge(fork, decompNode);
			Edge decomp2Join = myPolicy.createEdge(decompNode, join);

			for (Chain chain : originals) {
				@SuppressWarnings("unused")
				boolean ok = ChainHelper.composeChain(chain, fork, join,
						decompNode, fork2Decomp, decomp2Join);
				seqChains.add(chain);
			}

		}
		// Eliminating similar chains...
		Set<Chain> filteredChains = new HashSet<Chain>();
		for (Chain seqChain : seqChains) {
			boolean add = true;
			for (Chain filtered : filteredChains) {
				if (ChainHelper.areComparable(filtered, seqChain)) {
					add = false;
					break;
				}
			}
			if (add) {
				filteredChains.add(seqChain);
			}
		}

		return filteredChains;
	}

	/**
	 * Determines which node, of given chain is the first previous fork node,
	 * before given node and in the context of given Set of Chains.<BR/> Makes
	 * use of {@link IGraphSequencerPolicy#isFork(Node, Set)}.
	 * 
	 * @param chain
	 *            the {@link Chain} to be analyzed.
	 * @param node
	 *            the reference {@link Node}.
	 * @param allChains
	 *            the {@link Chain}s search context.
	 * @return the next fork node in the chain (may be null).
	 */
	public final Node getPreviousFork(final Chain chain
			, final Node node, final Set<Chain> allChains) {
		if (myPolicy == null || chain == null || node == null) {
			return null;
		}
		EList<Node> nodes = chain.getNodes();
		if (!nodes.contains(node)) {
			return null;
		}

		for (int i = nodes.indexOf(node) - 1; i > -1; i--) {
			Node current = nodes.get(i);
			if (myPolicy.isFork(current, allChains)) {
				return current;
			}
		}
		return null;
	}

	/**
	 * Determines which node, of given chain is the first fork node, after given
	 * node and in the context of given Set of Chains.<BR/>
	 * Makes use of
	 * {@link IGraphSequencerPolicy#isFork(Node, Set)}.
	 * 
	 * @param chain
	 *            the {@link Chain} to be analyzed.
	 * @param node
	 *            the reference {@link Node}.
	 * @param allChains
	 *            the {@link Chain}s search context.
	 * @return the next fork node in the chain (may be null).
	 */
	public final Node getNextFork(final Chain chain
			, final Node node, final Set<Chain> allChains) {
		if (myPolicy == null || chain == null || node == null) {
			return null;
		}
		EList<Node> nodes = chain.getNodes();
		int startIndex = 0;

		if (chain.getStartNode() == node) {
			startIndex = 0;
		} else {
			if (!nodes.contains(node)) {
				return null;
			}
			startIndex = nodes.indexOf(node);
		}
		for (int i = startIndex; i < nodes.size(); i++) {
			Node current = nodes.get(i);
			if (myPolicy.isFork(current, allChains)) {
				return current;
			}
		}
		return null;
	}

	/**
	 * Determines which node, of given chain is the first join node, after given
	 * node and in the context of given Set of Chains.<BR/>
	 * Makes use of {@link IGraphSequencerPolicy#isJoin(Node, Set)}.
	 * 
	 * @param chain
	 *            the {@link Chain} to be analyzed.
	 * @param node
	 *            the reference {@link Node}.
	 * @param allChains
	 *            the {@link Chain}s search context.
	 * @return the next join node in the chain (may be null).
	 */
	public final Node getNextJoin(final Chain chain
			, final Node node, final Set<Chain> allChains) {
		if (myPolicy == null || chain == null || node == null) {
			return null;
		}
		EList<Node> nodes = chain.getNodes();
		int startIndex = 0;

		if (chain.getStartNode() == node) {
			startIndex = 0;
		} else {
			if (!nodes.contains(node)) {
				return null;
			}
			startIndex = nodes.indexOf(node);
		}
		for (int i = startIndex; i < nodes.size(); i++) {
			Node current = nodes.get(i);
			if (myPolicy.isJoin(current, allChains)) {
				return current;
			}
		}
		return null;
	}

	/**
	 * Validates route to chains map :
	 * checks that each of the chains listed under a given route have
	 * this route's start and end nodes as {@link Chain#getStartNode()}
	 * and {@link Chain#getEndNode()}.
	 * @param map {@link Map<Route, Set<Chain>>}.
	 * @return see above.
	 */
	public static boolean isValidMap(final Map<Route, Set<Chain>> map) {
		for (Route route : map.keySet()) {
			Set<Chain> chains = map.get(route);
			Node start = route.getSource();
			Node end = route.getDestination();
			for (Chain chain : chains) {
				if (chain.getStartNode() != start
						|| chain.getEndNode() != end) {
					return false;
				}
			}
		}
		return true;
	}

}
